부산대학교자료구조
Scientific Inference Lab

Keys to Indices

Hash Functions

해시 함수(hash function)는 키를 0부터 m − 1 사이의 버킷 인덱스로 바꾼다. 같은 키에는 항상 같은 인덱스를 주어야 하고, 서로 다른 키는 가능한 한 고르게 퍼뜨려야 한다.

h(k) = k mod m나머지 연산은 결과를 항상 0부터 m − 1 사이로 만든다.
문자열 키문자별 ord 값을 합쳐 정수로 바꾼 뒤 나머지를 취한다.
원래 키도 저장해시 값이 같아도 키를 비교해 서로 구분한다.

나머지 연산은 어떤 정수 키도 유효한 인덱스로 바꾼다

키 k와 표 길이 m을 바꾸면 k mod m으로 계산한 버킷 인덱스와 같은 버킷에 모이는 키가 바뀐다.

위 줄은 버킷 인덱스 0부터 m − 1이며 초록 테두리 칸이 k가 가는 버킷이다. 아래 줄은 예시 키 10, 20, 30, 40, 50, 60의 버킷이며 파란 칸이 k와 같은 버킷에 모인 키다.

단순 합은 글자 순서를 무시하고, 위치 가중치가 순서를 반영한다

해시 방식을 바꾸면 cat과 act의 문자별 기여, 합계, 11로 나눈 버킷이 바뀐다.

행은 단어다. 칸마다 문자와 그 문자가 합계에 더하는 값이며, 마지막 열이 11로 나눈 버킷이다. 빨간 글자는 두 단어의 버킷이 같을 때다.